前言

雖然在 Day 14 我們有寫過一題構造 Binary Search Tree (文中會簡稱 BST)的題目，但還沒好好的看過這個結構，這個結構的相關題目應該算是基本分，特性明確，如果對這個結構不熟的人，務必趁這篇好好弄懂一下。

CRUD，增刪查改，資料結構的基本功能和基本操作，前面那題是 BST 的 C(建構)，今天會提到 R(查找)，接著明天我們會來看 U(改) 和 D(刪)，因為篇幅關係，我把 U 和 D 切到明天講會比較合適，今天如果練習完有餘裕，可以再回去練習一次 Day 14 的建構。

Search in a Binary Search Tree

給定一個 BST 的根結點，給一個值，搜尋該點在 BST 的位置並返回該節點，如果擁有該值的節點不存在，則返回空。
這題就是一個典型讓我們嘗試操作 BST 的題目。
讓我們再複習一次 BST 的定義：所有的左子樹的節點都會比根節點小，所有右子樹的節點都會比根節點大。
有了這個定義，這題再來就是照文字寫程式而已。

我們用遞迴來寫，SearchBST 這個函式的意義是：給予根節點與目標數值，回傳該節點。
終止條件是一旦碰到節點為 null，則表示有該數值的節點並不存在這棵樹中。
一旦找到相同的點，則回傳該點，如果該值比當前這個點的值大，且有該值的點存在，則必定存在右子樹中(見 BST 定義)，反之則在左子樹中。
有了這些，程式碼就自然而然了：

public class Solution {
    public TreeNode SearchBST(TreeNode root, int val) {
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        else if(root.val > val){
            return SearchBST(root.left, val);
        }
        else{
            return SearchBST(root.right, val);
        }
    }
    
}

遞迴我們應該在樹這個主題寫過不少，這題也算相對簡單的題目，能成功寫出來是好事，寫不出來可能要再想想遞迴的思路上是差了哪一點。

Validate Binary Search Tree

複習了 BST 的結構後，這題讓我們來驗證給定的一棵樹，判斷這棵樹是不是 BST，如果是，則回傳 True，否則回傳 False。

同樣，我們用遞迴結構來想。
終止條件，假設傳入的點為 null，則符合 BST 定義，回傳 True。
當前節點大於左子節點則回傳 False，且小於右子節點也回傳 False。
到這裡為止是合格的邏輯嗎？
這樣是直覺的想法，但再想過，會發現應該是有漏的。

   5
  / \
 4   7
/ \
3  6

如上面這棵樹，完全符合上面邏輯的敘述，但並不是 BST，因為 6 雖然小於父節點，但大於了 5，而 6 是 5 的左子樹中的一部份。
解決這個 case 的方式就是我們用走訪過的值來當邊際，保證邊際是單向收縮，不會先小於 5，結果過了幾個遞迴後大於 5 的節點反而通過。
我們的遞迴函式除了節點本身，多帶兩個節點進去遞迴，一個是 min，一個是 max，min 代表任一節點都必須大於 min，max 則表示任一節點都必須小於 max。
往下遞迴時，左子樹的 min 無須刷新，只要確認當前的 max 被刷新為現在節點(現在節點對左子樹來說是父節點，所有左子樹的節點都要小於這顆節點)；同理，右子樹的 max 無須刷新，而是確認接下來的右子樹節點都會比這顆節點大，所以刷新 min。
如果左右子樹都符合 BST 的定義，則這是一顆合法的 BST。

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return TraverseValid(root, null, null);
    }
    public bool TraverseValid(TreeNode root, TreeNode min, TreeNode max){
        if(root == null){
            return true;
        }
        if((min != null && root.val <= min.val)||(max != null && root.val >= max.val)){
            return false;
        }
        return TraverseValid(root.left, min, root) &&
            TraverseValid(root.right, root, max);
    }
}

寫完後，可以發現如果用這個邏輯去跑上面舉反例的樹，就能在遍歷到 4 的右子樹時透過 min 為 4，max 為繼承下來的 5，min 4 max 5 的範圍判斷出 6 在這裡會造成這棵樹不是一棵合法的 BST。
在遞迴中，可以透過這種額外帶入參數的方式，持續記憶需要逐層傳遞的數值或邊界擴增 / 收窄，會是一個常用的技巧，可以留意。